
// 297.二叉树的序列化与反序列化
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        // 使用前序遍历进行序列化
        // 对于nullptr使用#来表示
        string ret;
        function<void(TreeNode*)> dfs = [&](TreeNode* pos)
        {
            if(pos == nullptr) ret += " #";
            else 
            {
                ret += " " + to_string(pos->val);
                dfs(pos->left);
                dfs(pos->right);
            }
        };
        dfs(root);
        return ret;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        vector<string> prevorder;
        stringstream ss(data);
        string each;
        while(ss >> each)
            prevorder.push_back(move(each));

        int index = 0;
        function<TreeNode*()> dfs = [&]()->TreeNode*
        {
            if(prevorder[index] == "#") 
            {
                index++;
                return nullptr;
            }
            TreeNode* root = new TreeNode(stoi(prevorder[index++]));
            root->left = dfs();
            root->right = dfs();
            return root;
        };
        return dfs();
    }
};

// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));